UVa/216 - Getting in line/216.2.cpp

   1 /*
   2   Accepted
   3  */
   4 #include <cmath>
   5 #include <iostream>
   6 #include <algorithm>
   7 #include <vector>
   8 #include <queue>
   9
  10 #define popcount(x) __builtin_popcount(x)
  11
  12 using namespace std;
  13
  14 struct state{
  15   int i, v;
  16   double w;
  17   vector<int> o;
  18   state(int I, int V, double W, vector<int> O) : i(I), v(V), w(W), o(O) {}
  19   bool operator < (const state &that) const {
  20     return w > that.w;
  21   }
  22 };
  23
  24
  25 int main(){
  26   int n, N=1;
  27   while (cin >> n && n){
  28
  29     vector<pair<int, int> > p(n);
  30     for (int i=0; i<n; ++i){
  31       cin >> p[i].first >> p[i].second;
  32     }
  33
  34     double g[n][n];
  35     for (int i=0; i<n; ++i){
  36       for (int j=0; j<n; ++j){
  37         g[i][j] = hypot(p[i].first - p[j].first, p[i].second - p[j].second) + 16.0;
  38       }
  39     }
  40
  41     double d[1<<n][n];
  42     for (int i=0; i<(1<<n); ++i){
  43       for (int j=0; j<n; ++j){
  44         d[i][j] = 1E100;
  45       }
  46     }
  47
  48     priority_queue<state> q;
  49     for (int i=0; i<n; ++i){
  50       d[1<<i][i] = 0;
  51       q.push(state(i, 1<<i, 0.0, vector<int>(1, i)));
  52     }
  53
  54     while (q.size()){
  55       state top = q.top();
  56       q.pop();
  57
  58       //printf("Saqué de la pila: i = %d, v = %x, w = %lf\n", top.i, top.v, top.w);
  59
  60       if (d[top.v][top.i] < top.w) continue;
  61
  62       if (popcount(top.v) == n){ //Solution
  63         printf("**********************************************************\n");
  64         printf("Network #%d\n", N++);
  65         double t = 0.0;
  66         for (int i=0; i<n-1; ++i){
  67           printf("Cable requirement to connect (%d,%d) to (%d,%d) is %.2f feet.\n",
  68                  p[top.o[i]].first, p[top.o[i]].second,
  69                  p[top.o[i+1]].first, p[top.o[i+1]].second,
  70                  g[top.o[i]][top.o[i+1]]);
  71           t += g[top.o[i]][top.o[i+1]];
  72         }
  73         printf("Number of feet of cable required is %.2f.\n", t);
  74         break;
  75       }
  76
  77       for (int i=0; i<n; ++i){
  78         //printf("Intetando ir al vecino %d\n", i);
  79         if ((top.v & (1<<i)) == 0){ //Si no había visitado el i
  80           if (top.w + g[top.i][i] < d[top.v | (1<<i)][i]){
  81             d[top.v | (1<<i)][i] = top.w + g[top.i][i];
  82             top.o.push_back(i);
  83             q.push(state(i, top.v | (1<<i), top.w + g[top.i][i], top.o));
  84             top.o.erase(top.o.end() - 1);
  85           }
  86         }
  87       }
  88     }
  89   }
  90   return 0;
  91 }